package club.xiaojiawei.hash;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/22/22 12:51 PM
 * @question 205. 同构字符串
 * @description 给定两个字符串 s 和 t ，判断它们是否是同构的。
 * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
 * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
 */
public class IsIsomorphic205 {

    public static void main(String[] args) {
        IsIsomorphic205 test = new IsIsomorphic205();
        boolean result = test.isIsomorphic("eeggg", "aadda");
        System.out.println(result);
    }

    /**
     * 数组模拟哈希表
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        int[][] map1 = new int[128][];
        int[][] map2 = new int[128][];
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            int[] temp1 = map1[chars1[i]];
            int[] temp2 = map2[chars2[i]];
            if (temp1 == null){
                if (temp2 == null){
                    map1[chars1[i]] = new int[]{1, i};
                    map2[chars2[i]] = new int[]{1, i};
                }else {
                    return false;
                }
            }else if (temp2 == null){
                return false;
            }else if (temp1[0] != temp2[0]){
                return false;
            }else if (temp1[1] != temp2[1]){
                return false;
            }
            map1[chars1[i]][0]++;
            map2[chars2[i]][0]++;
        }
        return true;
    }

    /**
     * 启发-数组模拟哈希表（优化）
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic1(String s, String t) {
        int[] map1 = new int[128];
        int[] map2 = new int[128];
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (map1[chars1[i]] != map2[chars2[i]]){
                return false;
            }
            map1[chars1[i]] = map2[chars2[i]] = i + 1;
        }
        return true;
    }

    /**
     * 民间-数组模拟哈希表
     * @param text1
     * @param text2
     * @return
     */
    public boolean isIsomorphic2(String text1,String text2){
        int indexWord,indexLetter;
        int[] key =new int[128],value =new int[128];
        char[] word =text1.toCharArray(),letter =text2.toCharArray();
        for(int i=word.length-1;i>=0;i--){
            indexWord=word[i]+1;                                //將字元轉成對應的ASCII碼 +1是避免跟ASCII碼的0對應字元衝突到
            indexLetter=letter[i]+1;                            //將字元轉成對應的ASCII碼 +1是避免跟ASCII碼的0對應字元衝突到
            if(key[indexWord]==0 && value[indexLetter]==0){
                key[indexWord]=indexLetter;
                value[indexLetter]=indexWord;
            }else if(key[indexWord]!=indexLetter || value[indexLetter]!=indexWord)     //發現現在的字元對應跟之前紀錄的字元對應不同
                return false;
        }
        return true;
    }
}
